#include "big_int.h"

#include <utility>
#include <sstream>

big_int::big_int(): digits(1, 0), sign(false), shift(0)
{
}

big_int::big_int(int t = 0): digits(good_vector(1,abs(t))), sign(t < 0), shift(0)
{
}

big_int::big_int(const std::string s):sign(false), shift(0)
{
   std::string s1 = s;
   if (s1[0] == '-')
   {
      sign = true;
      s1 = s1.substr(1, s1.size() - 1);
   }
   for (int i = s1.length(); i > 0; i -= BASE_LENGTH) 
    {
        if (i >= BASE_LENGTH)
        {
            digits.push_back(atoi(s1.substr(i - BASE_LENGTH, BASE_LENGTH).c_str()));
        }
        else
        {
            digits.push_back(atoi(s1.substr(0, i).c_str()));
        }
    }
    delete_zeros();
}

void big_int::swap(big_int& b)
{
   digits.swap(b.digits);
   std::swap(sign, b.sign);
}

void swap(big_int& a, big_int& b)
{
   std::swap(a, b);
}

int big_int::compare_to(const big_int& b) const
{
   if (sign && !b.sign)
   {
      return -1;
   }  
   if (!sign && b.sign)
   {
      return 1;
   }
   if (sign)
      return abs(b).compare_to(abs(*this));
   if (length() + shift != b.length() + b.shift)
   {
      return length() + shift - b.length() - b.shift;
   }

   int i = length() - 1;
   int j = b.length() - 1;
   while ((i >= 0) && (j >= 0))
   {
      int diff = digits[i] - b.digits[j];
      if (diff != 0)
      {
         return diff;
      }
      i--;
      j--;
   }
   return i - j;
}

size_t big_int::length() const
{
   return digits.size();
}

void big_int::delete_zeros()
{
   size_t new_size = digits.size();
   while (new_size > 1 && !digits[new_size-1])
   {
      new_size--;
   }
   if (new_size == 1 && digits[new_size - 1] == 0)
   {
      sign = 0;
   }
   digits.resize(new_size);
}

bool operator==(const big_int& a, const big_int& b)
{
   return a.compare_to(b) == 0;
}

bool operator<(const big_int& a, const big_int& b)
{
   return a.compare_to(b) < 0;
}

bool operator>(const big_int& a, const big_int& b)
{
   return a.compare_to(b) > 0;
}

bool operator<=(const big_int& a, const big_int& b)
{
   return !(a > b);
}

bool operator>=(const big_int& a, const big_int& b)
{
   return !(a < b);
}

bool operator!=(const big_int& a, const big_int& b)
{
   return !(a == b);
}

big_int big_int::operator-() const
{
   big_int a(*this);
   if (a != 0)
   {
      a.sign = !a.sign;
   }
   return a;
}

big_int& big_int::operator <<=(size_t shift_)
{
   shift += shift_;
   return *this;
}

big_int& big_int::operator >>=(size_t shift_)
{
   shift -= shift_;
   return *this;
}

big_int operator <<(const big_int& a, size_t x)
{
   big_int t = a;
   return t <<= x;
}

big_int operator >>(const big_int& a, size_t x)
{
   big_int t = a;
   return t >>= x;
}

big_int& big_int::operator+=(const big_int& b)
{
   big_int a = *this;
   if (abs(a) < abs(b))
   {
      return (*this = (b + a));
   }
   if (a.sign)
   {
      return (*this = -((-a) + (-b)));
   }
    
   sign = false;
   shift = std::min(a.shift, b.shift);
   good_vector new_digits = good_vector(std::max(a.length() + a.shift, b.length() + b.shift)  + 1, 0);
   digits = new_digits;
   int s = (b.sign) ? -1 : 1;
   int carry = 0;
   for (size_t i = 0; i < length(); i++)
   {
      int t = 0;
      if ((a.shift <= shift + i) && (shift + i < a.shift + a.length()))
      {
         t += a.digits[i + shift - a.shift];
      }
      if ((b.shift <= shift + i) && (shift + i < b.shift + b.length()))
      {
         t += b.digits[i + shift - b.shift] * s;
      }
      t += carry;
      carry = 0;
      if (t >= BASE)
      {
         carry = 1;
         t -= BASE;
      }
      if (t < 0)
      {
         carry = -1;
         t += BASE;
      }
      digits[i] = t;
       
   }
   delete_zeros();
   return *this;
}

big_int& big_int::operator-=(const big_int& a)
{
   big_int ans =*this;
   ans += (-a);
   *this = ans;
   return *this;
}

big_int operator+(const big_int& a,const big_int& b)
{
   big_int t = a;
   return t += b;
}

big_int operator-(const big_int& a,const big_int& b)
{
   big_int t = a;
   return t -= b;
}

big_int& big_int::operator*=(const big_int& b)
{
   big_int a = *this;
   shift = a.shift + b.shift;
   sign = (a.sign ^ b.sign) & (a != 0) & (b != 0);
   size_t new_length = a.length() + b.length() + 1;
   good_vector new_digits(new_length, 0);
   digits = new_digits;
   for (size_t i = 0; i < a.length(); i++)
   {
      size_t carry = 0;
      for (size_t j = 0; j < b.length(); j++)
      {
         long long t = static_cast<long long>(a.digits[i]) * b.digits[j];
         digits[i + j] += t % BASE + carry;
         carry = static_cast<size_t>(t / BASE) + digits[i + j] / BASE;
         digits[i + j] %= BASE;
      }
      digits[i + b.length()] += carry;
      carry = digits[i + b.length()] / BASE;
      digits[i + b.length()] %= BASE;
      digits[i + b.length() + 1] = (carry != 0) ? carry : 0;
   }

   delete_zeros();
   return *this;
}

big_int operator*(const big_int& a, const big_int& b)
{  
   big_int t = a;
   return t *= b;
}

int big_int::find_divisor(const big_int& b)
{
   int l = 0;
   int r = BASE - 1;
   while (r - l > 0)
   {
       int m = (l + r + 1) / 2;
       if (compare_to(b * m) < 0)
       {
           r = m - 1;
       }
       else
       {
           l = m;
       }
   }
   return l;
}

big_int& big_int::operator/=(const big_int& v)
{
   big_int a = *this;
   big_int b = v;
   if (abs(a) < abs(b))
   {  
      *this = big_int(0);
      return *this;
   }
   big_int result = 0;
   result.sign = a.sign ^ b.sign & (a != 0) & (b != 0);
   result.shift = a.shift - b.shift;
   a.sign = false;
   b.sign = false;
   good_vector quotient(1, 0);
  
   big_int bb = b << (a.length() - b.length());
   while (bb.shift >= 0)
   {
      size_t q = a.find_divisor(bb);
      quotient.push_back(q);
      a = a - q * bb;
      bb >>= 1;
   }
   quotient.reverse();
   result.digits = quotient;
   result.delete_zeros();
   *this = result;
   return *this;
}

big_int operator/(const big_int& a, const big_int& b)
{
   big_int t = a;
   t /= b;
   return t;
}

big_int abs(big_int a)
{
   big_int ans = a;
   ans.sign = false;
   return ans;
}

big_int& big_int::operator%=(const big_int& b)
{  
   big_int a = *this;
   big_int t = b * (a / b); 
   *this = a - t;
   return *this;
}

big_int operator%(const big_int& a, const big_int& b)
{
   big_int t = a;
   return t %= b;
}

std::ostream& operator<<(std::ostream& os, const big_int& a)
{
   int n = a.length();
   while (a.digits[n - 1] == 0 && n > 1) 
      n--;
   if (n == 1 && a.digits[0] == 0)
   {
      os << "0";
      return os;
   }
   if (a.sign)
      os << "-";
   os << a.digits[n - 1];
   for (int i = n - 2; i >= 0; i--)
   {
      int now = a.digits[i];
      int tmp = now;
      int len = 0;
      for (len = 0; tmp > 9; tmp /= 10, len++);
      for (int i = 0; i < big_int::BASE_LENGTH - len - 1; i++)
         os << "0";
      os << now;
   }
   return os;
}

std::istream& operator>>(std::istream& is, big_int& a)
{
   std::string s;
   while (!is.eof() && isspace(is.peek()))
      is.get();
   if (is.eof())
   {
      is.setstate(std::ios::failbit);
      return is;
   }
   if (is.peek() == '+')
      is.get();
   else if (is.peek() == '-')
      s.push_back(is.get());
   if (is.eof()) 
   {
      is.setstate(std::ios::failbit);
      return is;
   }
   if (!isdigit(is.peek())) 
   {
      is.setstate(std::ios::failbit);
      return is;
   }
   while (!is.eof() && isdigit(is.peek()))
      s.push_back(is.get());
   a = big_int(s);
   return is;
}
